Java Fibonacci Series Recursive Optimized using Dynamic Programming

1. Overview

In this article, we will learn how to print the fibonacci series and find the nth fibonacci number using recursive approach.

Printing the Fibonacci series be done using the iterative approach using while and for loop.

In the following sections we will try to run the program for below scenarios.

• Print the fibonacci series for the given number
• Find the nth fibonacci number

In each approach, we will try to see the amount of time taken to process the logic and how it can be optimized using dynamic programming memoization technique.

2. Print the Fibonacci series using recursive way

Below program to display the first n Fibonacci number using recursive approach. For each input, we are going to print the time taken and compare for different inputs.

package com.javaprogramto.programs.numbers.fibonacii;

import java.time.Instant;

public class PrintFibonaciiSeriesRecursive {

	public static void main(String[] args) {

		long fibResult = 0;

		System.out.println("First 30 fibonacii series numbers : ");
		long startTime = Instant.now().toEpochMilli();

		for (int i = 1; i < 30; i++) {
			fibResult = fibonacii(i);
			System.out.print(fibResult + " ");
		}
		long endTime = Instant.now().toEpochMilli();

		System.out.println("\nExecution time " + (endTime - startTime) + " ms");

		System.out.println("\nFirst 50 fibonacii series numbers : ");
		startTime = Instant.now().toEpochMilli();

		for (int i = 1; i < 50; i++) {
			fibResult = fibonacii(i);
			System.out.print(fibResult + " ");
		}
		endTime = Instant.now().toEpochMilli();

		System.out.println("\nExecution time " + (endTime - startTime) + " ms");

	}

	// fibonacii recursive
	private static long fibonacii(long n) {

		if (n <= 2) {
			return 1;
		}
		long fibNumber = fibonacii(n - 1) + fibonacii(n - 2);

		return fibNumber;
	}
}

Output:

First 30 fibonacii series numbers : 
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 
Execution time 6 ms

First 50 fibonacii series numbers : 
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 
Execution time 53397 ms

From the output, we can understand that to print first 30 fibonacci numbers it took just 6 milli seconds but to print the first 50, it took around 54 seconds.

Time complexity: O(2^n)

Space complexity: 

3. Print the Fibonacci series using recursive way with Dynamic Programming

In the above program, we have to reduce the execution time from O(2^n).

If you observe the above logic runs multiple duplicates inputs.

Look at the below recursive internal calls for input n which is used to find the 5th Fibonacci number and highlighted the input values that are processed by our function multiple times.

2nd Fibonacci number is calculated 3 times.

3rd fibonacci number is calculated twice.

If the input value is 50 there are many inputs are reprocessed for the same inputs which kills the system.

From these analysis, if we can store these values in the memory we can avoid reprocessing them and retrieve the values from memory. This process is called as memoization.

Memoization make sure alway it runs for the different inputs and not for the same inputs again. Instead, gets the values from previous results from memory.

We can use HashMap for storing the intermediate key value pairs.

The below is the optimized program that takes less time for bigger inputs.

package com.javaprogramto.programs.numbers.fibonacii;

import java.time.Instant;
import java.util.Map;

import org.apache.commons.collections4.map.HashedMap;

public class PrintFibonaciiSeriesRecursiveOptimized {

	public static void main(String[] args) {

		long fibResult = 0;
		Map<Integer, Long> memory = new HashedMap<>();

		System.out.println("First 30 fibonacii series numbers : ");
		long startTime = Instant.now().toEpochMilli();

		for (int i = 1; i < 30; i++) {
			fibResult = fibonacii(i, memory);
			memory.clear();
			System.out.print(fibResult + " ");
		}
		long endTime = Instant.now().toEpochMilli();

		System.out.println("\nExecution time " + (endTime - startTime) + " ms");

		memory.clear();
		
		System.out.println("\nFirst 50 fibonacii series numbers : ");
		startTime = Instant.now().toEpochMilli();

		for (int i = 1; i < 50; i++) {
			fibResult = fibonacii(i, memory);
			memory.clear();
			System.out.print(fibResult + " ");
		}
		endTime = Instant.now().toEpochMilli();

		System.out.println("\nExecution time " + (endTime - startTime) + " ms");

	}

	// fibonacii recursive
		private static long fibonacii(int n, Map<Integer, Long> memory) {
			
			if(memory.get(n) != null) {
				return memory.get(n);
			}

			if (n <= 2) {
				return 1;
			}

			long fib = fibonacii(n - 1, memory) + fibonacii(n - 2, memory);
			
			memory.put(n, fib);
			
			return fib;
		}
}

Output:

First 30 fibonacii series numbers : 
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 
Execution time 2 ms

First 50 fibonacii series numbers : 
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 
Execution time 3 ms

From the above output, you can see the for bigger inputs just took 3ms which is fabulous. We brought down to 3 milli seconds from 54 seconds. 

This is the power of the dynamic programming technique.

4. Find the nth Fibonacci number using recursive way

The below example program to get the nth fibonacci number from the series recursively.

package com.javaprogramto.programs.numbers.fibonacii;

import java.time.Instant;

public class FindFibonaciiNumberRecursive {

	public static void main(String[] args) {
		long startTime = Instant.now().toEpochMilli();
		long finResult = fibonacii(30);
		long endTime = Instant.now().toEpochMilli();

		System.out.println("30th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");

		startTime = Instant.now().toEpochMilli();
		finResult = fibonacii(50);
		endTime = Instant.now().toEpochMilli();

		System.out.println("50th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");
	}

	
	// fibonacii recursive
	private static long fibonacii(long n) {

		if (n <= 2) {
			return 1;
		}

		return fibonacii(n - 1) + fibonacii(n - 2);
	}
}

Output:

30th fiboncaii number - 832040 execution time 5 ms
50th fiboncaii number - 12586269025 execution time 34413 ms

Take taken for 30th fibonacci number is 5 ms

50th Fibonacci number is 34 seconds.

Time Complexity - O(2^n)

Space Complexity - O(2^n)

5. Find the nth Fibonacci number using recursive way Using Dynamic Programming

Next, let us simplify the above code using memoization technique using hashmap. 

package com.javaprogramto.programs.numbers.fibonacii;

import java.time.Instant;
import java.util.HashMap;
import java.util.Map;

public class FindFibonaciiNumberRecursiveOptimized {

	public static void main(String[] args) {
		
		Map<Integer, Long> memory = new HashMap<>();
		
		long startTime = Instant.now().toEpochMilli();
		long finResult = fibonacii(30, memory);
		long endTime = Instant.now().toEpochMilli();

		System.out.println("30th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");

		// clearing the memoization map
		memory.clear();
		
		startTime = Instant.now().toEpochMilli();
		finResult = fibonacii(50, memory);
		endTime = Instant.now().toEpochMilli();

		System.out.println("50th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");
	}

	
	// fibonacii recursive
	private static long fibonacii(int n, Map<Integer, Long> memory) {
		
		if(memory.get(n) != null) {
			return memory.get(n);
		}

		if (n <= 2) {
			return 1;
		}

		long fib = fibonacii(n - 1, memory) + fibonacii(n - 2, memory);
		
		memory.put(n, fib);
		
		return fib;
	}
}

Output:

30th fiboncaii number - 832040 execution time 0 ms
50th fiboncaii number - 12586269025 execution time 0 ms

In this approach, if we want to calculate the 5th Fibonacci number from series, it calculates the only the lest side values from the recursive tree.

So, it reduces the logic execution from 2^n to n times.

Time Complexity : O(2^n)

Space Complexity : O(n) because it still holds the n level runtime stack.

6. Conclusion

In this article, we have seen how to implement the fibonacci series and find nth fibonacci number using recursive approach and optimized way using dynamic programming technique.

GitHub

Java Programs

HashMap Examples